package com.learn.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 前序遍历 中左右
 * 中序遍历 左中右
 * 后序遍历 左右中
 */
public class TreeOrder {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    //前序遍历
    public void preOrder(Node head) {
        if (head == null) {
            return;
        }
        System.out.println(head.value);
        preOrder(head.left);
        preOrder(head.right);
    }

    public void midOrder(Node head) {
        if (head == null) {
            return;
        }
        preOrder(head.left);
        System.out.println(head.value);
        preOrder(head.right);
    }

    public void lastOrder(Node head) {
        if (head == null) {
            return;
        }
        preOrder(head.left);
        preOrder(head.right);
        System.out.println(head.value);
    }


    /**
     * 层次遍历
     */
    public void LevelTraversal(Node head) {
        if (head == null) {
            return;
        }

        Queue<Node> nodes = new LinkedList<Node>();
        nodes.add(head);
        while (!nodes.isEmpty()) {
            Node poll = nodes.poll();
            System.out.println(poll.value);
            if (poll.left != null) {
                nodes.add(poll.left);
            }
            if (poll.right != null) {
                nodes.add(poll.right);
            }
        }

    }

}
